Conventionally, as illustrated in FIG. 1A, complex three dimensional (3-D) objects, or portions thereof, can be represented by collections of adjacent triangles (“a mesh”) representing the approximate geometry of the 3-D object, or by a geometry map, or surface, in two dimensional (2-D) surface space. One or more texture maps can be mapped to the surface to create a textured surface according to a texture mapping process. In a conventional graphics system, the surface geometry sampling happens before texture sampling. In this regard, signals textured over a surface can be very general, and can specify any sort of intermediate result that can be input to a shader procedure to produce a final color associated with a point sample, and thus need not specify a function of color or grey scale values.
After texture sampling, additional transformations can optionally be applied to the textured surface prior to rendering the image with picture elements (pixels) of a display device. Images in computer graphics are represented as a 2-D array of discrete values (grey scale) or as three 2-D arrays of discrete values (color). Using a standard (x, y, z) rectangular coordinate system, a surface can be specified as a mesh (e.g., triangle mesh) with an (x,y,z) coordinate per mesh vertex, or as a geometry map in which the (x,y,z) coordinates are specified as a rectilinear image over a 2D (u,v) coordinate system, called the surface parameterization domain. Texture map(s) can also be specified with the (u, v) coordinate system.
Point samples in the surface parametrization domain, where signals have been attached to the surface, including its geometry, can be generated from textured meshes or geometry maps. These samples can be transformed and shaded using a variety of computations. At the end of this transformation and shading processing, a point sample includes (a) positional information, i.e., an image address indicating where in the image plane the point maps to and (b) textured color, or grey scale, information that indicates the color of the sample at the position indicated by the positional information. Other data, such as depth information of the point sample to allow hidden surface elimination, can also be included. The transformed, textured surface is placed in a frame buffer prior to being rendered by a display in 2-D pixel image space (x, y). At this point, in the case of a black and white display device, each (x, y) pixel location in 2-D image space is assigned a grey value in accordance with some function of the surface in the frame buffer. In the case of a typical color display device, each (x, y) pixel location in 2-D image space is assigned red, green and blue (RGB) values. It is noted that a variety of color formats other than RGB exist as well.
In order to render the surface on the display device itself, conventionally, the textured surface is sampled at positions that reflect the centers of the pixels of the device on which the image is to be displayed. Conventionally, this sampling is performed by evaluating a function of the transformed, textured surface, at points that correspond to the center of each pixel, by mapping the centers of the pixels back into texture space to determine the point sample that corresponds to the pixel center.
In particular, the current rasterization architecture raster scans a triangle of the mesh to find the pixel centers it covers, and then maps each covered pixel center (x, y) back into texture space to get a texture location (u, v) that maps to each covered pixel center (x, y) along with some representation of the neighborhood of the (x, y) pixel center, e.g., by mapping x and y image tangent vectors back into texture space to get two vectors Vx and Vy. Then, for each pixel center covered by the triangle, the (u, v) point is used to define the filter center and Vx and Vy are used to define the filter shape to reconstruct a texture value for the pixel center.
Thus, the current rasterization architecture only samples at pixel centers, which is not an effective way to antialias images in all cases. For instance, in the current architecture, if the mesh is sub-divided into a greater number of smaller triangles, which is analogous to source sampling at a higher rate, at some point, the exact same image is nonetheless produced. Without increasing the image size, using smaller triangles fails to achieve antialiasing because most of these small triangles do not cover a pixel center and, as a result, are totally ignored by the current rasterization architecture. The current architecture works reasonably well when the texture map contains all the frequency information, because the texture can be represented as a pre-computed MIP-Map; however, true anisotropic filtering is very costly for the present architecture to achieve. If the frequency information is stored as a per-vertex signal over the geometry, or is due to boundaries between separate meshes, i.e., if the frequency information is not represented as a pre-filtered texture map, then the only way to antialias is to increase image resolution, otherwise known as supersampling.
It would thus be desirable to accumulate and filter over all point samples that map to bin(s), such that the more point samples a bin receives, the better the antialiasing is with respect to that bin. It would also be desirable to provide a mechanism to control the number of samples received by the bin(s), to provide a controllable level of antialiasing in accordance with application tradeoffs and frequency of source content. Thus, there is a need for an improved graphics architecture and techniques that overcome the limitations of the conventional graphics architecture.
Forward mapping, or rendering algorithms that sample content and then map samples onto a display surface, have become more appealing recently. Forward mapping directly maps surface data onto the image plane. For each surface element, the renderer maps the point onto the image plane. Thus, once the destination image has been selected, the process transitions through each sample of the source image in order, e.g., scan-line order, an order determined by tiling, an order that addresses interleaving (swizzling), etc., and determines its position in the destination image.
Example applications include image based rendering (IBR), volume rendering and rendering of extremely complex scenes. For instance, sampling at the source rather than the destination of an imaging process is a standard technique in video applications. In these methods, source image samples are mapped to the destination to reconstruct and resample an image at the display sample rate. If separable filters are employed, the process can be decomposed into cascaded one dimensional (1-D) interpolation and filtering. Typical practice in computer graphics as described above, whether in polygon rasterizers or ray tracers, has been the opposite—to map destination samples backward into texture source space.
It is clear, however, that dealing with problems in maintaining image quality with forward mapping approaches requires (1) care in adjusting the source sampling rate to adequately capture detail and (2) care in reconstructing and resampling the destination signal to eliminate aliasing. While both points remain a problem for present forward mapping approaches, the second consideration is particularly a weak point and thus a forward mapping approach that adequately addresses both problems is currently desired.
Thus, recent publications have described methods that map samples forward from source to destination. Such forward mapping approaches have several advantages over the traditional architecture, which first maps display samples back to the texture domain to reconstruct the destination signal. Forward mapping (1) avoids unnecessary rasterization and interpolation over complicated geometric primitives like triangles, (2) better exploits coherence in the source signal, since it can be visited in optimal order instead of one that depends on how the textured geometry projects to the texture domain and (3) treats antialiasing of geometry and texture uniformly, avoiding redundant texture filtering that occurs when supersampling to antialias the geometry. Forward mapping, however, can result in holes in an image that undergoes transformation, e.g., image warping, perspective transformation, etc., because some pixels in the destination image are not “filled in” by any locations from the source image, and are effectively left blank by the mapping. See, for illustration, FIG. 1B. Generally speaking, the severity of space left empty by such a forward mapping process can increase with the complexity or severity of change introduced by a transformation. Moreover, when there are multiple layers of objects in the z-plane of the image space, some of which should occlude others, a hole in a first object at the forefront of the image may reveal a second object through the hole.
Current forward mapping approaches employ complex schemes to avoid the above-described undersampling that leaves gaps, or holes, between mapped samples where the source signal is magnified, but such complex approaches are presently inadequate for a variety of reasons. Attempts to employ source-based sampling for 3-D surface rendering have been made, and research papers have proposed some source-based sampling schemes, but these attempts and schemes have not achieved any commercial success. For volume rendering, extremely simple forward mapping algorithms can be used, but these algorithms disadvantageously have large destination footprints.
Specifically, Grossman and Dally propose using a minimal sampling rate in the source space and then filling in gaps with a hierarchical averaging scheme. The QSplat system stores surface samples in a hierarchical data structure and avoids holes by rasterizing projected spherical primitives that bound the surface. The “surfels” algorithm uses a hole filling routine similar to Grossman and Dally, but exploits area primitive rasterization, or “visibility splatting,” to detect holes.
In brief, currently proposed forward mapping schemes propose to handle this “hole” problem either (1) by rasterizing big geometric “splats” (of variable size) instead of points so that z-buffer values are rasterized for the entire big splat and nothing shows throw, or (2) by performing the image interpolation in places where no splat was mapped using a z-pyramid that prevents occluded objects from showing through an occluding object. These methods, however, are very complex and introduce computational overhead in terms of both computing time and other resources like memory bandwidth. For example, the first technique moves away from the elegant idea of, and thus the information embodied by, point samples and ends up rasterizing area elements, in essence returning to the conventional architecture described above. Also, these techniques essentially use a z-buffer over a pixel grid to resolve hidden surfaces, and so only take account of one splat, i.e., the frontmost splat, per pixel, and thus potentially eliminate content that should be reflected by the end result.
Additionally, designing hardware specifically for IBR requires careful attention to the order and timing of memory access. In this regard, one problem with present techniques is that they do not target applications that combine conventional graphics with IBR and video. Memory access remains a central problem, and an architecture tuned to IBR alone and ignoring 3D graphics is insufficient. The geometric database for a typical real-time rendering application is such that surface elements project to areas smaller than the spacing between display samples. The futility of rasterizing such tiny elements has led to the need for new, forward-mapping rendering architectures, some recent proposals for which, as mentioned above, devote considerable effort to eliminating gaps between mapped samples.
Hence, several areas for improvement remain in presently proposed architectures. For instance, a question that needs to be determined in connection with source sampling is how much source sampling is enough. To answer this question, some source-frequency-based sampling criteria must be utilized. Some approaches assume a sampling rate in accordance with the resolution of the display device. A drawback of such an approach is that to sample content at the resolution of the display device inherently assumes that a single sampling rate is appropriate for all portions of the image. However, different parts of an image may have different frequencies. For example, significant change in pixel intensity occurs at the edge of an object or texture, e.g., at the edges of the stripes of a zebra, and thus exhibits high frequencies. In contrast, over a smooth surface of an object with uniform color, there is little change and thus the region can be represented with fewer samples. Thus, in order to capture an appropriate level of detail in the image, it would be desirable to sample one portion of the image at one frequency, and another portion of the image at a different frequency, and so on, for different regions of the surface being sampled.
Moreover, another question that needs to be determined is how to ensure that sufficient coverage is achieved by the source sampling in the destination to avoid the complicated hole-filling work of previous forward mapping approaches. To answer this question, some geometric-coverage criteria must also be utilized. Grossman and Dally describe a criterion that guarantees coverage given a uniform, rectangular destination sampling lattice, whereby the length of the longest side of an (imaginary) triangle mesh through the mapped source samples must not exceed the distance between destination samples. Based on this criterion, it is further observed by Grossman and Dally that improved efficiency results from a hexagonal source sampling, forming equilateral triangles which are less likely to have unbalanced triangle edge lengths after mapping. Such a source sampling is typically not convenient to obtain, however, requiring special-purpose image resampling. Additionally, evaluating this metric at numerous source samples is impractical.
Another question is how to sufficiently antialias in such a system. In low-cost, real-time systems, antialiasing is achieved by standard oversampling followed by filtering and decimation. Mitchell, for example, uses a non-linear process to reconstruct images from irregularly scattered samples for ray tracing.
A different antialiasing approach that has been used in both forward and traditional inverse-mapped graphics is signal pre-filtering, a technique that resamples the source signal at various levels of frequency content as a preprocessing step. Unfortunately, for 3-D graphics and even for perspectively transformed 2-D graphics, effective pre-filtering is difficult. The standard MIP-Map pyramid approach constructs a 1-D sequence of increasingly decimated signal versions, but the decimation is isotropic and thus blurs too much, or alternatively, “leaks” aliasing, if one direction in the source signal is minified more than another. This is a common effect of projections of 3-D geometry near silhouettes and foreshortened 2-D perspective transformations. As a result, inverse-mapping 3-D graphics hardware is moving toward anisotropic filtering of greater sophistication and extent of anisotropy handled, but at the expense of computational complexity. Moreover, aliasing problems due to “minification”, where high frequency source content is compressed into a small region in the destination, has always been a problem for present techniques and thus there is a need for a technique that addresses the minification case in a superior manner. Present forward-mapping approaches, e.g., the technique provided Grossman and Dally, thus far have either ignored minification aliasing, or have used MIP-Map pyramids that fail to address the need for anisotropic filtering.
Additionally, in order to make best use of available hardware, many existing forward mapping schemes have been shoehorned into a conventional polygon rendering pipeline. However, to fully realize its benefits, forward mapping merits a new architecture. While specialized IBR processor have been proposed, there is a clear need in the art for architectures that are more programmable.
In brief, while present rasterization architectures can effectively antialias signals represented as texture maps, it is due to such architectures' use of expensive backward mapping and on-the-fly trilinear and anisotropic filtering. Signals not represented as texture maps can only be antialiased by supersampling.
It would thus be desirable to improve upon present rasterization architectures that sample only at pixel centers and presently proposed forward mapping architectures by providing a process that resolves over all samples received by bin(s), whereby effective antialiasing is achieved by generating more samples at the source, without adding any more bin(s). It would be further desirable to provide a process that filters over all point samples that lie in a bin, no matter how many are present. It would be still further desirable to provide a controllable sampling process that ensures that each bin receives at least a predetermined number of samples.